package likou;

import java.util.Random;

/**
 * @author zp
 * @version 1.0
 * @description: 打乱数组
 * @date 2022/3/25 17:14
 *
 * Fisher-Yates 洗牌算法
 * 思路和算法
 *
 * 考虑通过调整 \textit{waiting}waiting 的实现方式以优化方法一。
 *
 * 我们可以在移除 \textit{waiting}waiting 的第 kk 个元素时，将第 kk 个元素与数组的最后 11 个元素交换，然后移除交换后数组的最后 11 个元素，这样我们只需要 O(1)O(1) 的时间复杂度即可完成移除第 kk 个元素的操作。此时，被移除的交换后数组的最后 11 个元素即为我们根据随机下标获取的元素。
 *
 * 在此基础上，我们也可以不移除最后 11 个元素，而直接将其作为乱序后的结果，并更新待乱序数组的长度，从而实现数组的原地乱序。因为我们不再需要从数组中移除元素，所以也可以将第 kk 个元素与第 11 个元素交换。
 *
 * 具体地，实现算法如下：
 *
 * 设待原地乱序的数组 \textit{nums}nums。
 * 循环 nn 次，在第 ii 次循环中（0 \le i < n0≤i<n）：
 * 在 [i,n)[i,n) 中随机抽取一个下标 jj；
 * 将第 ii 个元素与第 jj 个元素交换。
 * 其中数组中的 \textit{nums}[i \ .. \ n-1]nums[i .. n−1] 的部分为待乱序的数组，其长度为 n-in−i；\textit{nums}[0 \ .. \ i-1]nums[0 .. i−1] 的部分为乱序后的数组，其长度为 ii。
 *
 */
public class Solution {
    int[] nums;
    int[] original;

    public Solution(int[] nums) {
        this.nums = nums;
        this.original = new int[nums.length];
        System.arraycopy(nums, 0, original, 0, nums.length);
    }

    public int[] reset() {
        System.arraycopy(original, 0, nums, 0, nums.length);
        return nums;
    }

    public int[] shuffle() {
        Random random = new Random();
        for (int i = 0; i < nums.length; ++i) {
            int j = i + random.nextInt(nums.length - i);
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }
}
